package com.rr.middle;

import java.util.*;

/**
 * @author RR
 * @date 2024/7/13 21:38
 */

/**
 * https://leetcode.cn/problems/find-if-array-can-be-sorted/?envType=daily-question&envId=2024-07-13
 */
public class CanSortArray {

    public boolean canSortArray(int[] nums) {
        int preBitNum = 0;
        int lastMax = 0;
        int currentMax = 0;
        for (int num : nums) {
            int bitNum = this.getBitNum(num);
            if (preBitNum == bitNum) {
                currentMax = Math.max(currentMax, num);
            } else {
                preBitNum = bitNum;
                lastMax = currentMax;
                currentMax = num;
            }
            if (num < lastMax) {
                return false;
            }
        }
        return true;
    }

    /**
     * 第一次的解法，不是最优解，没有注意到只能相邻元素调换的条件
     * @param nums
     * @return
     */
    public boolean canSortArray2(int[] nums) {
        // Map<1的位数，Set<对应的数字>>
        Map<Integer, Set<Integer>> bitNumMap = new HashMap<>();
        Map<Integer, Integer> numBitMap = new HashMap<>();
        // 每个数字对应的下标
        Map<Integer, Integer> numIndexMap = new HashMap<>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int bitNum = getBitNum(nums[i]);
            bitNumMap.computeIfAbsent(bitNum, k -> new HashSet<>()).add(i);
            numBitMap.put(nums[i], bitNum);
            numIndexMap.put(nums[i], i);
        }
        Arrays.sort(nums);
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            Integer index = numIndexMap.get(num);
            Integer bitNum = numBitMap.get(num);
            Set<Integer> positions = bitNumMap.get(bitNum);
            int min = Math.min(i, index);
            int max = Math.max(i, index);
            for (int j = min; j <= max; j++) {
                if (!positions.contains(j)) {
                    return false;
                }
            }
        }
        return true;
    }

    private int getBitNum(int num) {
        int result = 0;
        int tmp = 8;
        while (num > 0) {
            int pow = 1 << tmp;
            if (num >= pow) {
                num -= pow;
                result++;
            }
            tmp--;
        }
        return result;
    }

    public static void main(String[] args) {
        CanSortArray canSortArray = new CanSortArray();
        canSortArray.canSortArray(new int[]{75, 34, 30});
    }
}
